#include <iostream>
using namespace std;

#include <string>
#include <unordered_map>

class Solution {
public:
    string reorganizeString(string s)
    {
        unordered_map<char, int> hash;
        char maxVal = 0;
        int maxCount = 0;

        for (auto& c : s)
        {
            if (maxCount < ++hash[c])
            {
                maxCount = hash[c];
                maxVal = c;
            }
        }

        int n = s.size();
        string ret(n, 0);
        int index = 0;
        for (int i = 0; i < maxCount; i++)
        {
            if (index >= n)
                index = 1;

            ret[index] = maxVal;
            index += 2;
        }

        hash.erase(maxVal);

        for (auto& [x, y] : hash)
        {
            for (int i = 0; i < y; i++)
            {
                if (index >= n)
                    index = 1;

                ret[index] = x;
                index += 2;
            }
        }

        for (int i = 1; i < n; i++)
        {
            if (ret[i - 1] == ret[i])
                return "";
        }

        return ret;
    }
};

int main()
{
    string s = "aab";
    Solution ss;
    auto ret = ss.reorganizeString(s);
    
    return 0;
}